package 二叉树;

import com.sun.deploy.util.StringUtils;
import com.sun.jmx.snmp.SnmpNull;
import 链表.Node;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 二叉树路径问题
 * <p>
 * 1、
 * <p/>
 * User: zhaixiaolong Date:2024/2/29 8:51 ProjectName: algorithm Version:
 */
public class 二叉树路径 {

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(5,
                new TreeNode(4, new TreeNode(11, new TreeNode(5), new TreeNode(2)), null),
                new TreeNode(8, new TreeNode(9), new TreeNode(4, null, new TreeNode(1))));

        targetPathSum(treeNode, 22);

    }

    /**
     * 路径总和
     * 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，
     * 这条路径上所有节点值相加等于目标和 targetSum 。
     * 叶子节点 是指没有子节点的节点
     *
     * @param treeNode  树根节点
     * @param targetSum 目标路径和
     * @return 路径节点节点值
     */
    public static void targetPathSum(TreeNode treeNode, int targetSum) {
        LinkedList<TreeNode> path = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        findTargetPathSum(treeNode, targetSum, path, 0, res);
        if (res.size() > 0) {
            res.forEach(list -> {
                System.out.println(Arrays.toString(list.toArray()));
            });
        }
    }

    /**
     * 寻找路径总和
     *
     * @param currNode 当前节点
     * @param targetSum 目标累计
     * @param path 当前遍历路径
     * @param pathSum 当前路径累计和
     * @param res 结果，累计和等于targetSum的路径
     */
    public static void findTargetPathSum(TreeNode currNode, int targetSum, LinkedList<TreeNode> path, Integer pathSum, List<List<Integer>> res) {
        path.add(currNode);
        pathSum += currNode.val;
        if (pathSum == targetSum && currNode.getLeft() == null && currNode.getRight() == null) {
            res.add(path.stream().map(TreeNode::getVal).collect(Collectors.toList()));
        }
        if (currNode.getLeft() != null) {
            if (pathSum < targetSum) {
                // 继续向下遍历
                findTargetPathSum(currNode.left, targetSum, path, pathSum, res);
            }
            // 回溯
            path.removeLast();
            if (path.size() == 0) {
                return;
            }
        }
        if (currNode.getRight() != null) {
            if (pathSum < targetSum) {
                // 继续向下遍历
                findTargetPathSum(currNode.right, targetSum, path, pathSum, res);
            }
            // 回溯
            TreeNode pre = path.removeLast();
            if (path.size() == 0) {
                return;
            }
        }
    }

    /**
     * 二叉树的所有路径
     * 给定一个二叉树，返回所有从根节点到叶子节点的路径
     *
     * @param treeNode
     * @return
     */
    public static List<String> treePaths(TreeNode treeNode) {
        // 所有路径
        List<String> result = new ArrayList<>();
        // path
        LinkedList<Integer> path = new LinkedList<>();
        // 递归
        traversal(treeNode, path, result);
        return result;
    }

    /**
     * 二叉树的所有路径——回溯
     *
     * @param current
     * @param path
     * @param result
     */
    public static void traversal(TreeNode current, LinkedList<Integer> path, List<String> result) {
        path.add(current.val);
        // 路径保存
        if (current.getLeft() == null && current.getRight() == null) {
            // 叶子节点了
            StringBuilder stringBuilder = new StringBuilder();
            for (int i = 0; i < path.size() - 1; i++) {
                stringBuilder.append(path.get(i) + "——>");
            }
            stringBuilder.append(path.get(path.size() - 1));
            result.add(stringBuilder.toString());
            return;
        }
        if (current.getLeft() != null) {
            traversal(current.left, path, result);
            //回溯
            path.removeLast();
        }
        if (current.getRight() != null) {
            traversal(current.right, path, result);
            //回溯
            path.removeLast();
        }
    }

    //结果
    int result = 0;

    /**
     * 给定一个二叉树，它的每个结点都存放着一个整数值
     * 找出路径和等于给定数值的路径总数。
     * 路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
     * 二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
     * @param root
     * @param targetSum
     * @return
     */
    public int pathSum3(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        //根节点
        traversal(root, targetSum);
        //左子树递归
        pathSum3(root.left, targetSum);
        //右子树递归
        pathSum3(root.right, targetSum);
        return result;
    }

    /**
     * @return void
     * @Description: 深度优先遍历
     * @author 三分恶
     * @date 2021/7/12 22:03
     */
    void traversal(TreeNode root, int sum) {
        if (root == null) {
            return;
        }
        //路径和
        sum -= root.val;
        //不需要到达叶子节点,路径和满足要求即可
        if (sum == 0) {
            //结果添加
            result++;
        }
        //递归左子树
        traversal(root.left, sum);
        //递归右子树
        traversal(root.right, sum);
    }
}
